package 哈夫曼树;
import java.util.PriorityQueue;
import java.util.Queue;
public class HFMtree{
	private HTreeNode root;
	private HTreeNode[] nodes;
	public class HTreeNode implements Comparable<HTreeNode>{		
		String s;
		int weight;
		private HTreeNode left;
		private HTreeNode right;		
		public HTreeNode(int weight){
			this.weight = weight;
		}		
		public HTreeNode(int weight, HTreeNode left, HTreeNode right){
			this.weight = weight;
			this.left = left;
			this.right = right;
	            	}
		public int compareTo(HTreeNode o){
			return new Integer(this.weight).compareTo(new Integer(o.weight));
		           }	
	}
	public void createHFMTree(int[] weights){ 
		Queue<HTreeNode> nodeQueue = new PriorityQueue<HTreeNode>();
		nodes = new HTreeNode[weights.length];
		for(int i=0; i<weights.length; i++){
			nodes[i] = new HTreeNode(weights[i]);
			nodeQueue.add(nodes[i]);
			
		}
		while(nodeQueue.size() > 1){
			HTreeNode left = nodeQueue.poll();
			HTreeNode right = nodeQueue.poll();
			HTreeNode parent = new HTreeNode(left.weight + right.weight, left, right);
			nodeQueue.add(parent);
			
		}
		root = nodeQueue.poll();	
	}
	public void output(HTreeNode head){
		if(head != null){
			System.out.println(head.weight);
			output(head.left);
			output(head.right);
		   }
	       }
	public void encode(HTreeNode node, String s){
		if(node != null){
			node.s = s;
			encode(node.left, node.s+"0");
			encode(node.right, node.s+"1");
		}
	}
	public void printTreeCode(String[] sa, int[] weights){
		for(int i=0; i<weights.length; i++){
			System.out.println(sa[i] +":" + nodes[i].s);
		}
	} 	
	public static void main(String[] args) {
		int[] weights = new int[]{7, 8, 2, 1, 1};
		String[] sa = new String[]{"a","b","c","d","e",};		
		HFMtree huffmanTree = new HFMtree();
	    huffmanTree.createHFMTree(weights);
	    huffmanTree.output(huffmanTree.root);
	    huffmanTree.encode(huffmanTree.root, "0");
	    huffmanTree.printTreeCode(sa, weights);
	}
}